#include <iostream>
using namespace std;

// 递归
unsigned long long pell1(int k)
{
    if(k == 1 || k == 2)
        return k;

    unsigned long long x = (2*pell1(k-1)) % 32767;
    unsigned long long y = (  pell1(k-2)) % 32767;

    return (x + y)%32767;
}

// 递推
unsigned long long pell2(int k)
{
    unsigned long long a_1 = 1;
    unsigned long long a_2 = 2;

    if(k == a_1 || k == a_2)
        return k;

    unsigned long long a_3;
    for(int i=3; ; i++)
    {
        a_1 %= 32767;
        a_2 %= 32767;
        a_3 = 2*a_2 + a_1;
        a_3 %= 32767;

        if(i == k)
            return a_3;

        a_1 = a_2;
        a_2 = a_3;
    }
}

int main(int argc, char const *argv[])
{
    int n;
    cin >> n;

    int k[n];
    for(int i=0; i<n; i++)
        cin >> k[i];

    // 递归算法：递归太深会导致栈溢出
    // for(int i=0; i<n; i++)
    //     cout << pell1(k[i]) << endl;

    // 递推算法
    for(int i=0; i<n; i++)
        cout << pell2(k[i]) << endl;
    
    return 0;
}
